package com.liuzhilong.infrastructure.framework.algorithms.datastruct.line;

import lombok.AccessLevel;
import lombok.Data;
import lombok.Setter;
import lombok.experimental.Accessors;

import java.util.Objects;
import java.util.Random;
import java.util.function.Consumer;
import java.util.function.Function;

/**
 * <h2>跳表</h2>
 * <p>
 *     跳表是一种升级的链表结构。正常的链表，查询某个key通常要遍历一遍，这个复杂度是O(n).
 *      跳表是对查询做了优化的链表。
 * </p>
 * <img class="marble" src="SkipList.jpg" alt="">
 * <p>
 *  从上图来看，跳表的逻辑结构是分层的链表。最底层是全部数据的列表，往上都是索引层。越往上越稀疏。当某一层的node有索引的时候，从这层开始向下，每层都有索引。
 * </p>
 * <pre>
 *     代码核心是
 *         //从height 高度开始找 经过遍历之后，preNode在第一层，并且preNode.next(0)是空或者大于等于checkNode
 *         Node<T> preNode = head;
 *         for (int i = height-1; i >-0 ; i--) {
 *             //从i层开始，一直循环到key小于等于preNode.next
 *             while (preNode.next(i)!=null&& gt(checkNode,preNode.next(i))) {
 *                 preNode = preNode.next(i);
 *             }
 *         }
 * </pre>
 */
public class SkipList<T extends Comparable<T>>  {
    /**
     * header 这个header不会放数据<T> 作用直接标记一下跳表的开始。删除也不会删除他。
     */
    @Setter(AccessLevel.PRIVATE)
    @Accessors(chain = true)
    public Node<T> head = null;
    /**
     * 索引的最大高度
     */
    @Setter(AccessLevel.PRIVATE)
    @Accessors(chain = true)
    private int maxHeight=16;
    /**
     * 用于{@link #insert(Comparable)}的时候，给这个node指定next索引的高度。这部分需要利用数学的模型，使高一层的索引数量是
     * 低一层的1/2,这样整体的搜索效率趋近于O(log(N))
     */
    public static final Function<Integer, Integer> heightPolicy = (maxHeight) -> {
        Random random = new Random();
        int height = 1;
        //每次有二分之一的概率 使height自增一
        for (int i = 0; i < maxHeight && random.nextInt() < 0.5f; i++) {
            height++;
        }
        return height;
    };


    /**
     * 索引的高度 这个会每次更新
     */
    private int height=1;


    public static final <T extends Comparable<T>> SkipList<T> create(Integer maxHeight){
        return new SkipList<T>().setMaxHeight(maxHeight).setHead(Node.create(maxHeight));
    }

    /**
     * <p>从最高层开始，一层一层向下找</p>
     * @param key
     * @return
     */
    public T find(T key){
        Node<T> preNode = head;
        Node<T> checkNode = Node.create(maxHeight, key);
        //从height 高度开始找
        for (int i = height-1; i >=0 ; i--) {
            //从i层开始，一直循环到key小于等于preNode.next
            while (preNode.next(i)!=null&& gt(checkNode,preNode.next(i))) {
                preNode = preNode.next(i);
            }
        }
        //经过以上遍历之后，preNode在第一层，并且preNode.next(0)是空或者大于等于checkNode
        if(preNode.next(0)!=null&&eq(checkNode,preNode.next(0))){
            return preNode.next(0).getKey();
        }
        return null;
    }

    /**
     * 插入流程
     * @param key
     */
    public void insert(T key) {
        int newNodeHeight = heightPolicy.apply(maxHeight);
        Node<T> preNode = head;
        // 不让用泛型数组。烦人。
        Object[] holder = new Object[newNodeHeight];
        for (int i = 0; i < holder.length; i++) {
            holder[i] = head;
        }
        Node<T> checkNode = Node.create(maxHeight, key);
        //从height 高度开始找
         for (int i = height-1; i >=0 ; i--) {
            //从i层开始，一直循环到key小于等于preNode.next
            while (preNode.next(i)!=null&& gt(checkNode,preNode.next(i))) {
                preNode = preNode.next(i);
            }
            if(i<newNodeHeight){
                holder[i] = preNode;
            }
        }

        //已经存在的 报异常
        if(preNode.next(0)!=null&&eq(checkNode,preNode.next(0))){
            throw new IllegalArgumentException("已经存在的key["+key+"]");
        }

        //如果没有 插入新节点

        Node<T> newNode = Node.create(maxHeight, newNodeHeight, key);
        // 针对每一层进行插入
        for (int i = newNodeHeight-1; i >=0 ; i--) {
            Node<T> preNodei = (Node<T>)holder[i];
            newNode.next(i,preNodei.next(i));
            preNodei.next(i, newNode);
        }
        this.height = newNodeHeight > height ? newNodeHeight : height;
    }

    /**
     * 删除流程
     * @param key
     */
    public T delete(T key) {
        Node<T> preNode = head;
        // 不让用泛型数组。烦人。
        Object[] holder = new Object[height];
        for (int i = 0; i < holder.length; i++) {
            holder[i] = head;
        }
        Node<T> checkNode = Node.create(maxHeight, key);
        //从height 高度开始找
        for (int i = height-1; i >=0 ; i--) {
            //从i层开始，一直循环到key小于等于preNode.next
            while (preNode.next(i)!=null&& gt(checkNode,preNode.next(i))) {
                preNode = preNode.next(i);
            }
            holder[i] = preNode;
        }

        // 如果没有 报没有这个key
        if(!(preNode.next(0)!=null&&eq(checkNode,preNode.next(0)))){
            return null;
        }


        //删除
        Node<T> deleteNode = preNode.next(0);
        //删除每个级联的
        for (int i = height-1; i >=0 ; i--) {
            Node<T> prei = (Node<T>) holder[i];
            if((prei).next(i)!=null&&eq(deleteNode,(prei).next(i))){
                prei.next(i, deleteNode.next(i));
                deleteNode.next(i, null);
            }
        }
        return deleteNode.getKey();
    }

    public void print(){
        String blank = "->";
        //一层一层打印
        for (int i = height-1; i >=0 ; i--) {
            StringBuffer sb = new StringBuffer();
            sb.append("F  ->  ");
            Node<T> next = head.next(0);
            Node<T> nextLink = head.next(i);
            while(next!=null){
                if(Objects.equals(next,nextLink)){
                    sb.append(nextLink.getKey());
                    nextLink = nextLink.next(i);
                }else{
                    sb.append(blank);
                }
                sb.append("  ");
                next = next.next(0);
            }
            System.out.println(sb);
        }

    }


    private boolean gt(Node s, Node t){
        return s.compareTo(t) > 0;
    }
    private boolean eq(Node s, Node t){
        return Objects.equals(s,t);
    }

    private SkipList(){

    }

    /**
     * 节点 这里只对key做了封装，如果需要挂载数据，就在加一个value的泛型。
     *
     * @param <T>
     */
    @Data()
    @Accessors(chain = true)
    private static class Node<T extends Comparable<T>> implements Comparable<Node<T>> {
        //挂载的数据
        private T key;

        private Object[] next;

        private Integer indexHeight ;
        public void next(int i, Node<T> node) {
            next[i] = node;
        }

        public Node<T> next(int i) {
            return (Node<T>) next[i];
        }

        public static final <TT extends Comparable<TT>> Node<TT> create(int height,int indexHeight, TT data) {
            Node<TT> result = create(height);
            return result.setKey(data).setIndexHeight(indexHeight);
        }

        public static final <TT extends Comparable<TT>> Node<TT> create(int height, TT data) {
            Node<TT> result = create(height);
            return result.setKey(data);
        }

        public static final <TT extends Comparable<TT>> Node<TT> create(int height) {
            return new Node<TT>().setNext(new Object[height]);
        }


        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node<?> node = (Node<?>) o;
            return Objects.equals(key, node.key);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }

        @Override
        public int compareTo(Node<T> o) {
            return this.key.compareTo(o.key);
        }
        private Node(){

        }
    }


}
